package org.lql.algo.codecrush.week006;

/**
 * @author: liangqinglong
 * @date: 2025-08-07 17:49
 * @description: 75. 颜色分类 <a href="https://leetcode.cn/problems/sort-colors/description/">...</a>
 **/
public class SortColors {


	/**
	 * 给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
	 * <p>
	 * 我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
	 * <p>
	 * 必须在不使用库内置的 sort 函数的情况下解决这个问题。
	 * <p>
	 * <p>
	 * <p>
	 * 示例 1：
	 * <p>
	 * 输入：nums = [2,0,2,1,1,0]
	 * 输出：[0,0,1,1,2,2]
	 * 示例 2：
	 * <p>
	 * 输入：nums = [2,0,1]
	 * 输出：[0,1,2]
	 * <p>
	 * <p>
	 * 提示：
	 * <p>
	 * n == nums.length
	 * 1 <= n <= 300
	 * nums[i] 为 0、1 或 2
	 *
	 * @param nums
	 */
	public void sortColors(int[] nums) {
		int low = 0, mid = 0, high = nums.length - 1;

		while (mid <= high) {
			if (nums[mid] == 0) {
				swap(nums, low, mid);
				low++;
				mid++;
			} else if (nums[mid] == 1) {
				mid++;
			} else { // nums[mid] == 2
				swap(nums, mid, high);
				high--;
			}
		}
	}

	private void swap(int[] nums, int i, int j) {
		int temp = nums[i];
		nums[i] = nums[j];
		nums[j] = temp;
	}

	public static void main(String[] args) {
		SortColors sortColors = new SortColors();
		int[] nums = new int[]{2, 0, 2, 1, 1, 0};
		sortColors.sortColors(nums);
		for (int num : nums) {
			System.out.print(num + " ");
		}
	}
}
